570D - Tree Requests - CodeForces Solution

#include <bits/stdc++.h>


// author: aykhn

using namespace std;

typedef long long ll;

#define OPT ios_base::sync_with_stdio(0); \
            cin.tie(0); \
            cout.tie(0)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pss pair<long,long>
#define all(v) v.begin(), v.end()
#define mpr make_pair
#define pb push_back
#define ts to_string
#define fi first
#define se second
#define ins insert
#define inf 0x3F3F3F3F
#define infll 0x3F3F3F3F3F3F3F3FLL
#define bpc __builtin_popcount
#define print(v) for(int i = 0; i < v.size(); i++) cout << v[i] << " "; cout<<endl;

int n;
string s;
vector<int> adj[2000001];
vector<pii> d[2000001];
int p[2000001];
int key[2000101];
int e[2000001];
int tim;

void dfs(int a, int de)
{
    key[a] = ++tim;
    if (d[de].size() == 0) d[de].pb(mpr(key[a], (1 << (s[a - 1] - 'a'))));
    else d[de].pb(mpr(key[a], d[de].back().se ^ (1 << (s[a - 1] - 'a'))));

    for (int &v : adj[a]) dfs(v, de + 1);

    e[a] = ++tim;
}

int main()
{
    OPT;
    int m;
    cin >> n >> m;

    for (int i = 2; i <= n; i++)
    {
        cin >> p[i];
        adj[p[i]].pb(i);
    }
    cin >> s;
    
    dfs(1, 1);

    while (m--)
    {
        int v, h;
        cin >> v >> h;

        int x = lower_bound(all(d[h]), mpr(key[v], -1)) - d[h].begin();
        int y = lower_bound(all(d[h]), mpr(e[v], -1)) - d[h].begin() - 1;

        if (y < 0)
        {
            cout << "Yes" << endl;
            continue;
        }
        int val = 0;
        if (x > 0) val = d[h][y].se ^ d[h][x - 1].se;
        else val = d[h][y].se;
        cout << (bpc(val) <= 1 ? "Yes" : "No") << endl;
    }
}